// run: $exec < input
#include <iostream>
#include <cassert>

long long mo = 1000000009;
long long k, d, m;

long long quick(long long a, long long b)
{
	assert(a >= 0);
	assert(b >= 0);
	if (!b) return 1;
	long long ret = quick(a, b / 2);
	ret = (ret * ret) % mo;
	if (b & 1) return ret = (ret * a) % mo;
	return ret;
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin >> k >> d >> m;
	if (m % d) { std::cout << "0\n"; return 0; }
	long long td = d, tm = m;
	long long ans = 1;
	for (long long i = 2; i * i <= m; i++) {
		long long t1 = 0, t2 = 0;
		for (; !(td % i); td /= i) t1++;
		for (; !(tm % i); tm /= i) t2++;
		long long len = t2 - t1 + 1;
		assert(t2 >= t1);
		if (len == 1) continue;
		long long tmp = quick(len, k) - 2 * quick(len - 1, k) + quick(len - 2, k);
		tmp %= mo;
		ans = (ans * tmp) % mo;
	}
	if (tm > 1) {
		long long i = tm;
		long long t1 = 0, t2 = 0;
		for (; !(td % i); td /= i) t1++;
		for (; !(tm % i); tm /= i) t2++;
		long long len = t2 - t1 + 1;
		if (len != 1) {
			long long tmp = quick(len, k) - 2 * quick(len - 1, k) + quick(len - 2, k);
			tmp %= mo;
			ans = (ans * tmp) % mo;
		}
	}
	ans += mo;
	ans %= mo;
	std::cout << ans << '\n';
}

